namespace AdvancedTraining.Lesson34;

/// <summary>
/// 井字棋游戏设计
/// 本题测试链接 : https://leetcode.cn/problems/design-tac-toe/
///
/// 设计一个井字棋游戏，可以在n x n的棋盘上进行游戏，并能够判断游戏胜负。
///
/// 算法思路：
/// 1. 使用计数器数组来高效跟踪每个玩家在每行、每列、两条对角线上的棋子数
/// 2. 每次落子后更新相关计数器
/// 3. 检查是否有计数器达到n（胜利条件）
/// 4. 时间复杂度：O(1) per move，空间复杂度：O(n)
/// </summary>
public class DesignTicTacToe //leetcode_0348
{
    /// <summary>
    /// 井字棋游戏类
    /// </summary>
    public class TicTacToe
    {
        // 记录每个玩家在每行上的棋子数
        // rows[a][1] : 1这个人，在a行上，下了几个
        // rows[b][2] : 2这个人，在b行上，下了几个
        private readonly int[][] _rows;
        // 记录每个玩家在每列上的棋子数
        private readonly int[][] _cols;
        // 记录每个玩家在左对角线上的棋子数
        // leftUp[2] = 7 : 2这个人，在左对角线上，下了7个
        private readonly int[] _leftUp;
        // 记录每个玩家在右对角线上的棋子数
        // rightUp[1] = 1，在右对角线上，下了9个
        private readonly int[] _rightUp;
        // 记录棋盘状态，防止重复落子
        private readonly bool[][] _matrix;
        // 棋盘大小
        private readonly int _n;

        /// <summary>
        /// 构造函数，初始化n×n的井字棋棋盘
        /// </summary>
        /// <param name="n">棋盘大小</param>
        public TicTacToe(int n)
        {
            _rows = new int[n][];
            _cols = new int[n][];
            for (int i = 0; i < n; i++)
            {
                _rows[i] = new int[3]; // 0 1 2
                _cols[i] = new int[3];
            }
            _leftUp = new int[3];
            _rightUp = new int[3];
            _matrix = new bool[n][];
            for (int i = 0; i < n; i++)
            {
                _matrix[i] = new bool[n];
            }
            _n = n;
        }

        /// <summary>
        /// 在指定位置落子
        /// </summary>
        /// <param name="row">行号</param>
        /// <param name="col">列号</param>
        /// <param name="player">玩家编号 (1或2)</param>
        /// <returns>如果落子导致该玩家获胜，返回玩家编号，否则返回0</returns>
        public int Move(int row, int col, int player)
        {
            // 检查该位置是否已经有棋子
            if (_matrix[row][col])
            {
                return 0; // 重复落子，返回0表示没有获胜
            }

            // 标记该位置已占用
            _matrix[row][col] = true;

            // 更新相关计数器
            _rows[row][player]++;
            _cols[col][player]++;

            // 如果在左对角线上，更新左对角线计数器
            if (row == col)
            {
                _leftUp[player]++;
            }

            // 如果在右对角线上，更新右对角线计数器
            if (row + col == _n - 1)
            {
                _rightUp[player]++;
            }

            // 检查是否有计数器达到n（胜利条件）
            if (_rows[row][player] == _n || _cols[col][player] == _n ||
                _leftUp[player] == _n || _rightUp[player] == _n)
            {
                return player; // 返回获胜的玩家
            }

            return 0; // 没有人获胜
        }
    }

    /// <summary>
    /// 测试井字棋游戏设计
    /// </summary>
    public static void Run()
    {
        Console.WriteLine("井字棋游戏设计算法测试开始");

        // 测试用例1: 基本功能测试 - 玩家1纵向三连获胜
        Console.WriteLine("测试用例1: 基本功能测试 (n=3)");
        var game1 = new TicTacToe(3);
        var result1 = game1.Move(0, 0, 1);
        Console.WriteLine($"Move(0,0,1): {result1} (期望: 0)");
        var result2 = game1.Move(0, 1, 2);
        Console.WriteLine($"Move(0,1,2): {result2} (期望: 0)");
        var result3 = game1.Move(1, 0, 1);
        Console.WriteLine($"Move(1,0,1): {result3} (期望: 0)");
        var result4 = game1.Move(1, 1, 2);
        Console.WriteLine($"Move(1,1,2): {result4} (期望: 0)");
        var result5 = game1.Move(2, 0, 1); // 玩家1在第一列三连
        Console.WriteLine($"Move(2,0,1): {result5} (期望: 1 - 玩家1获胜)");

        // 测试用例2: 1x1棋盘，单步获胜
        Console.WriteLine("\n测试用例2: 1x1棋盘，单步获胜");
        var game2 = new TicTacToe(1);
        var result6 = game2.Move(0, 0, 1);
        Console.WriteLine($"Move(0,0,1): {result6} (期望: 1 - 玩家1获胜)");

        // 测试用例3: 左对角线三连获胜
        Console.WriteLine("\n测试用例3: 左对角线三连 (n=3)");
        var game3 = new TicTacToe(3);
        var result7 = game3.Move(0, 0, 1);
        Console.WriteLine($"Move(0,0,1): {result7} (期望: 0)");
        var result8 = game3.Move(0, 1, 2);
        Console.WriteLine($"Move(0,1,2): {result8} (期望: 0)");
        var result9 = game3.Move(1, 1, 1);
        Console.WriteLine($"Move(1,1,1): {result9} (期望: 0)");
        var result10 = game3.Move(1, 0, 2);
        Console.WriteLine($"Move(1,0,2): {result10} (期望: 0)");
        var result11 = game3.Move(2, 2, 1); // 玩家1左对角线三连
        Console.WriteLine($"Move(2,2,1): {result11} (期望: 1 - 玩家1获胜)");

        // 测试用例4: 右对角线三连获胜
        Console.WriteLine("\n测试用例4: 右对角线三连 (n=3)");
        var game4 = new TicTacToe(3);
        var result12 = game4.Move(0, 2, 1);
        Console.WriteLine($"Move(0,2,1): {result12} (期望: 0)");
        var result13 = game4.Move(0, 0, 2);
        Console.WriteLine($"Move(0,0,2): {result13} (期望: 0)");
        var result14 = game4.Move(1, 1, 1);
        Console.WriteLine($"Move(1,1,1): {result14} (期望: 0)");
        var result15 = game4.Move(1, 0, 2);
        Console.WriteLine($"Move(1,0,2): {result15} (期望: 0)");
        var result16 = game4.Move(2, 0, 1); // 玩家1右对角线三连
        Console.WriteLine($"Move(2,0,1): {result16} (期望: 1 - 玩家1获胜)");

        // 测试用例5: 玩家2获胜
        Console.WriteLine("\n测试用例5: 玩家2纵向三连获胜 (n=3)");
        var game5 = new TicTacToe(3);
        var result17 = game5.Move(0, 0, 1);
        Console.WriteLine($"Move(0,0,1): {result17} (期望: 0)");
        var result18 = game5.Move(0, 1, 2);
        Console.WriteLine($"Move(0,1,2): {result18} (期望: 0)");
        var result19 = game5.Move(1, 0, 1);
        Console.WriteLine($"Move(1,0,1): {result19} (期望: 0)");
        var result20 = game5.Move(1, 1, 2);
        Console.WriteLine($"Move(1,1,2): {result20} (期望: 0)");
        var result21 = game5.Move(2, 2, 1);
        Console.WriteLine($"Move(2,2,1): {result21} (期望: 0)");
        var result22 = game5.Move(2, 1, 2); // 玩家2在第二列三连
        Console.WriteLine($"Move(2,1,2): {result22} (期望: 2 - 玩家2获胜)");

        Console.WriteLine("\n井字棋游戏设计算法测试结束");
    }
}